package com.leetcode.leetcode.anyan;

/**
 * 顺便复习：Java异或运算，位移运算
 *  异或：异或运算(^)是以二进制数据为基础进行运算的。
 *  异域中同位如果值相同(都是0或者都是1)则为0，不同(一个是0，一个是1)为1。
 *
 *  java中有三种移位运算符
 *      <<   :   左移运算符，num << 1,相当于num乘以2
 *      >>   :   右移运算符，num >> 1,相当于num除以2, 带符号右移。正数右移高位补0，负数右移高位补1。
 *      >>>  :   无符号右移，忽略符号位，空位都以0补齐, 无论是正数还是负数，高位通通补0。对于正数而言，>>和>>>没区别。
 *      例如：10的二进制是1010，左移一位变成10100，十进制是20
 */

/**
 *  &（与运算） 两个操作数中位都为1，结果才为1，否则结果为0
 *  |（或运算）两个位只要有一个为1，那么结果就是1，否则就为0
 *  ～（非运算）如果位为0，结果是1，如果位为1，结果是0
 */
public class _剑指_Offer_56_I_数组中数字出现的次数 {

    /**
     * 一个整型数组 nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n)，空间复杂度是O(1)。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：nums = [4,1,4,6]
     * 输出：[1,6] 或 [6,1]
     * 示例 2：
     *
     * 输入：nums = [1,2,10,4,1,4,3,3]
     * 输出：[2,10] 或 [10,2]
     *  
     *
     * 限制：
     *
     * 2 <= nums.length <= 10000
     *
     * 来源：力扣（LeetCode）
     * 链接：https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-lcof
     * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
     */

    static class Solution {
        public static int[] singleNumbers(int[] nums) {
            int ret = 0;
            for (int i = 0; i < nums.length; i++) {
                ret ^= nums[i];
            }
            /**
             * 查找ret第一个为1的位，说明这两个数的二进制形式在这一位上是不同的，是给nums分组的标准
             * 两个一样的数异或结果是0；转成二进制，位一样的两个数一样异或是0，不一样是1
             * 分组的目的是把要找的两个数分到不同的组，组内其他数异或之后都会被抵消，得到的结果就是要找的这个数
             */
            int div = 1;//&：都是1结果才是1，div初始化为1，如果ret & div的结果是1，说明ret是1
            while ((ret & div) == 0) {
                div <<= 1;
            }
            int a = 0;
            int b = 0;
            for(int n: nums) {
                if((div & n) == 0) {
                    a ^= n;
                } else {
                    b ^= n;
                }
            }
            return new int[]{a,b};
        }
        public static void main(String[] args) {
            int[] nums = {4,1,4,6};
            nums = singleNumbers(nums);
            System.out.println(nums[0]);
            System.out.println(nums[1]);
        }
    }
}
